import java.util.*;

/*
* 算法：暴力迭代
*
* 思路：
* 1. 用迭代遍历，计算出所有
* 2. 用栈保存所有路径，同时用集来保存路径长度值
* */
public class Solution_2 {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root==null)
        {
            return false;
        }


        //保存所有路径栈的列表
        List<Stack<TreeNode>> stackList = new ArrayList<>();
        TreeNode point = root;
        Stack<TreeNode> path = new Stack<>();
        path.push(root);
        Set<TreeNode> nodeSet = new HashSet<>();
        while (point!=null) {
            if(point.left!=null&&!nodeSet.contains(point.left))
            {
                nodeSet.add(point.left);
                path.push(point.left);
                point = point.left;
            }else if(point.right!=null&&!nodeSet.contains(point.right)) {
                nodeSet.add(point.right);
                path.push(point.right);
                point = point.right;
            }
            else {
                if(point.left==null&&point.right==null)
                {stackList.add((Stack<TreeNode>) path.clone());}
                path.pop();
                if(path.isEmpty())
                {
                    break;
                }
                point = path.peek();
            }
        }

        for (Stack<TreeNode> stack: stackList) {

            int sum = 0;
            while (!stack.isEmpty())
            {
                sum+=stack.pop().val;
            }
            if(sum==targetSum)
            {
                return true;
            }
        }
        return false;
    }
}
